package pro.softzhang.algo.lc600;

import pro.softzhang.algo.flag.difficulty.DRed;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 */
@DRed
public class LC649_Dota2Senate {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public String predictPartyVictory(String senate) {
            int n = senate.length();
            Queue<Integer> radiant = new LinkedList<>(), dire = new LinkedList<>();
            for(int i = 0; i < n; i++) {
                char ch = senate.charAt(i);
                if (ch == 'R') radiant.offer(i);
                else dire.offer(i);
            }

            while (!radiant.isEmpty() && !dire.isEmpty()) {
                int ridx = radiant.poll(), didx = dire.poll();
                if (ridx < didx) radiant.offer(ridx + n);
                else dire.offer(didx + n);
            }

            return radiant.isEmpty() ? "Dire" : "Radiant";
        }
    }
}
